/**
 此法未通过第67用例，待排查问题
 * @param {number} n
 * @param {number[]} blacklist
 */
var Solution = function (n, blacklist) {
  blacklist.sort((a, b) => a - b)
  this.blacklist = blacklist
  this.n = n
}

/**
 * @return {number}
 */
Solution.prototype.pick = function () {
  const range = this.n - this.blacklist.length
  const rdm = Math.floor(Math.random() * range)
  // console.log('pick start', `rdm = ${rdm}`)
  const [idx] = this.bisect(rdm)
  if (idx === -1) return rdm
  const newTarget = rdm + idx + 1
  let res = this.checkInBlacklist(newTarget, rdm)
  return res === -1 ? rdm : res
}

Solution.prototype.checkInBlacklist = function (target, otarget = null, left = null) {
  const [idx, isInBlacklist] = this.bisect(target, left)
  if (idx === -1) return -1
  const newTarget = otarget + idx + 1
  // console.log('checkInBlacklist',`target = ${target}, idx = ${idx}, isInBlackList = ${isInBlacklist}, newTarget = ${newTarget}`)
  if (isInBlacklist) {
    return this.checkInBlacklist(newTarget, otarget, idx)
  } else {
    return newTarget
  }
}

Solution.prototype.bisect = function (target, left) {
  // 二分查找找出target是哪个黑名单或黑名单之后
  left = left || 0
  let right = this.blacklist.length - 1
  let idx = -1
  while (left <= right) {
    const mid = (left + right) >> 1
    const blackItem = this.blacklist[mid]
    if (blackItem === target) {
      return [mid, true]
    } else if (target > blackItem) {
      idx = mid
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return [idx, false]
}

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(n, blacklist)
 * var param_1 = obj.pick()
 */
